let rec select0 f ls =
  match ls with
  | [] -> failwith "select0"
  | x::xs ->
    let compare (m, ms) n ->
      if f n m then (n, m::ms)
      else (m, n::ms)
    List.fold compare (x, []) xs

let rec select f ls =
  match ls with
  | [] -> failwith "select"
  | [x] -> (x, [])
  | x::xs ->
    let (m, ms) = select xs
    if f m x then (m, x::ms)
    else (x, xs)

let rec find_min ls =
  match ls with
  | [] -> failwith "find_min"
  | [x] -> (x, [])
  | x::xs ->
    let (m, ms) = find_min xs
    if m < x then (m, x::ms)
    else (x, xs)

let rec selection_sort ls =
  match ls with
  | [] -> []
  | _ ->
    let (m, ms) = find_min ls
    m :: selection_sort ms

let test =
  [3; 7; 4; 1; 9; 10; 5; 8; 2; 6]
  |> selection_sort
  |> printfn "%A"
